// synch.cc 
//	Routines for synchronizing threads.  Three kinds of
//	synchronization routines are defined here: semaphores, locks 
//   	and condition variables (the implementation of the last two
//	are left to the reader).
//
// Any implementation of a synchronization routine needs some
// primitive atomic operation.  We assume Nachos is running on
// a uniprocessor, and thus atomicity can be provided by
// turning off interrupts.  While interrupts are disabled, no
// context switch can occur, and thus the current thread is guaranteed
// to hold the CPU throughout, until interrupts are reenabled.
//
// Because some of these routines might be called with interrupts
// already disabled (Semaphore::V for one), instead of turning
// on interrupts at the end of the atomic operation, we always simply
// re-set the interrupt state back to its original value (whether
// that be disabled or enabled).
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "synch.h"
#include "system.h"

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	Initialize a semaphore, so that it can be used for synchronization.
//
//	"debugName" is an arbitrary name, useful for debugging.
//	"initialValue" is the initial value of the semaphore.
//----------------------------------------------------------------------

Semaphore::Semaphore(char* debugName, int initialValue)
{
    name = debugName;
    value = initialValue;
    queue = new List;
}

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	De-allocate semaphore, when no longer needed.  Assume no one
//	is still waiting on the semaphore!
//----------------------------------------------------------------------

Semaphore::~Semaphore()
{
    delete queue;
}

//----------------------------------------------------------------------
// Semaphore::P
// 	Wait until semaphore value > 0, then decrement.  Checking the
//	value and decrementing must be done atomically, so we
//	need to disable interrupts before checking the value.
//
//	Note that Thread::Sleep assumes that interrupts are disabled
//	when it is called.
//----------------------------------------------------------------------

void
Semaphore::P()
{
    IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts
    
    while (value == 0) { 			// semaphore not available
	queue->Append((void *)currentThread);	// so go to sleep
	currentThread->Sleep();
    } 
    value--; 					// semaphore available, 
						// consume its value
    
    (void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
}

//----------------------------------------------------------------------
// Semaphore::V
// 	Increment semaphore value, waking up a waiter if necessary.
//	As with P(), this operation must be atomic, so we need to disable
//	interrupts.  Scheduler::ReadyToRun() assumes that threads
//	are disabled when it is called.
//----------------------------------------------------------------------

void
Semaphore::V()
{
    Thread *thread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    thread = (Thread *)queue->Remove();
    if (thread != NULL)	   // make thread ready, consuming the V immediately
	scheduler->ReadyToRun(thread);
    value++;
    (void) interrupt->SetLevel(oldLevel);
}

// Dummy functions -- so we can compile our later assignments 
// Note -- without a correct implementation of Condition::Wait(), 
// the test case in the network assignment won't work!

//----------------------------------------------------------------------
// Lock::Lock
// 	Initialize a lock, so that it can be used for synchronization.
//
//	"debugName" is an arbitrary name, useful for debugging.
//	"isBusy" is the status of the lock, can be free(FALSE) or busy(TRUE)
//      "ownerThread" is the pointer to the thread holding the lock
//      "queue" is the queue for threads waiting to use the lock
//----------------------------------------------------------------------
Lock::Lock(char* debugName) {
    name = debugName;
    status = FREE;
    ownerThread = NULL;
    queue = new List;
}

//----------------------------------------------------------------------
// Lock::~Lock
// 	De-allocate lock, when no longer needed.  Assume no one
//	is still waiting on the lock!
//----------------------------------------------------------------------
Lock::~Lock() {
    //delete ownerThread;
	ownerThread = NULL;
    delete queue;
}


//----------------------------------------------------------------------
// Lock::Acquire
// 	Acquire a lock for the thread. If the lock is used by another
//      thread, put itself to the lock waiting queue and sleep; otherwise
//      take ownership of the lock and proceed.
//----------------------------------------------------------------------

void Lock::Acquire() {
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    // If current thread is the owner of the lock, do not attempt
    // to acquire the lock again, just return.
    if (isHeldByCurrentThread()) {
        DEBUG('s', "Owner thread \"%s\" attempting to acquire the lock \"%s\"\n", ownerThread->getName(), getName());
		printf("Owner thread \"%s\" attempting to acquire the lock \"%s\"\n", ownerThread->getName(), getName());
        (void) interrupt->SetLevel(oldLevel);
        return;
    }

    // If the lock is not held by anyone else, take ownership of
    // the lock, and set the lock to BUSY status; otherwise, add
    // self to the queue waiting for the lock and sleep.
    if (status == FREE) {
        status = BUSY;
        ownerThread = currentThread;
    }
    else {
        queue->Append((void *)currentThread);
#ifdef USER_PROGRAM
			//processTableLock->Acquire();
		if(currentThread->process!=NULL){
			currentThread->process->decreaseActiveThreadCount();
			currentThread->process->increaseWaitThreadCount();
		}
			//processTableLock->Release();
#endif
        currentThread->Sleep();
#ifdef USER_PROGRAM
			//processTableLock->Acquire();
		if(currentThread->process!=NULL){
			currentThread->process->decreaseWaitThreadCount();
			currentThread->process->decreaseSignalThreadCount();
		}
			//processTableLock->Release();
#endif
    }

    (void) interrupt->SetLevel(oldLevel);
}

//----------------------------------------------------------------------
// Lock::Release
// 	Release a lock for the thread. If the lock is owned by the thread,
//      release it, otherwise, do not release. If some other threads are
//      also waiting on the lock, wake up the first one waiting for it,
//      make it the owner of the lock; otherwise, make the lock free.
//----------------------------------------------------------------------
void Lock::Release() {
    Thread *thread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    // If the thread is not the owner and is attempting to release
    // the lock, do not do anything, return.
    if (!isHeldByCurrentThread()) {
        DEBUG('s', "Not owner thread \"%s\" attempting to release the lock \"%s\"\n", currentThread->getName(), getName());
		printf("Not owner thread \"%s\" attempting to release the lock \"%s\"\n", currentThread->getName(), getName());
        (void) interrupt->SetLevel(oldLevel);
	return;
    }

    // The lock owner thread is releasing the lock, but first check
    // to see if any other thread is waiting on the lock, if there
    // is one, remove it from the queue, make it the lock owner,
    // and move it to the scheduler; otherwise, make the lock FREE
    // and remove the ownership. 
    if (!queue->IsEmpty()) {
        thread = (Thread *)queue->Remove();
        if (thread != NULL) {
#ifdef USER_PROGRAM
			//processTableLock->Acquire();
			//thread->process->increaseActiveThreadCount();
			//thread->process->increaseSignalThreadCount();
			//processTableLock->Release();
#endif
            ownerThread = thread;
            scheduler->ReadyToRun(thread);
        }
    }
    else {
        status = FREE;
        ownerThread = NULL;
    }

    (void) interrupt->SetLevel(oldLevel);
}

//----------------------------------------------------------------------
// Lock::isHeldByCurrentThread
// 	Check to see if the current thread is the one holding the lock.
//----------------------------------------------------------------------
bool Lock::isHeldByCurrentThread() {
    return (ownerThread == currentThread);
}

//----------------------------------------------------------------------
// Lock::isBusy
// 	Check to see if the current lock is being used.
//----------------------------------------------------------------------
bool Lock::isBusy() {
	if (ownerThread != NULL) {
		return TRUE;
	}
	else {
		return FALSE;
	}
}

//----------------------------------------------------------------------
// Lock::Condition
// 	Initialize a condition variable, so that it can be used for synchronization.
//
//	"debugName" is an arbitrary name, useful for debugging.
//	"waitingLock" is lock associated with the condition variable, used
//          to determine whether the threads are dealing with the same condition
//          variable
//      "queue" is the queue for threads waiting with the same lock
//----------------------------------------------------------------------
Condition::Condition(char* debugName) {
    name = debugName;
    waitingLock = NULL;
    queue = new List;
}

//----------------------------------------------------------------------
// Lock::~Condition
// 	De-allocate condition variable, when no longer needed.  Assume no one
//	is still waiting on the conditoin variable!
//----------------------------------------------------------------------
Condition::~Condition() {
    //delete waitingLock;
	waitingLock = NULL;
    delete queue;
}

//----------------------------------------------------------------------
// Condition::Wait
// 	Wait on the condition variable with a lock. If the thread is holding
//      a lock, first release the lock, then sleep itself, and then when
//      woken up by Signal, try to re-acquire the lock and proceed.
//----------------------------------------------------------------------
void Condition::Wait(Lock* conditionLock) {
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    // If the thread is tyring to wait CV with a lock and the thread
    // isn't the owner of the lock, then we shouldn't proceed at all.
    if (!conditionLock->isHeldByCurrentThread()) {
		DEBUG('s', "Thread \"%s\" is trying to wait without the lock \"%s\" held by it\n", currentThread->getName(), conditionLock->getName());
		printf("Thread \"%s\" is trying to wait without the lock \"%s\" held by it\n", currentThread->getName(), conditionLock->getName());
        (void) interrupt->SetLevel(oldLevel);
        return;
    }

    // If the lock associated with the condition variable is NULL,
    // then something is wrong. The thread should have a proper lock,
    // return.
    if (conditionLock == NULL) {
        DEBUG('s', "Thread \"%s\" is trying to wait with NULL lock\n", currentThread->getName());
		printf("Thread \"%s\" is trying to wait with NULL lock\n", currentThread->getName());
        (void) interrupt->SetLevel(oldLevel);
        return;
    }

    // If the lock associated with the condition variable is NULL, then 
    // the thread is the first one to wait with the lock, associate the lock
    // with the condition variable to make sure all threads waiting are waiting
    // with the same lock.
    if (waitingLock == NULL) {
        waitingLock = conditionLock;
    }

    // If the thread is waiting with a different lock not associated with
    // the condition variable, something else is wrong.  Do not proceed
    // further, return instead.
    if (waitingLock != conditionLock) {
        //DEBUG('s', "Thread \"%s\" is trying to wait with DIFFERENT lock \"%s\" instead of \"%s\"\n", currentThread->getName(), conditionLock->getName(), waitingLock->getName());
		printf("Thread \"%s\" is trying to wait with DIFFERENT lock \"%s\" instead of \"%s\"\n", currentThread->getName(), conditionLock->getName(), waitingLock->getName());
        (void) interrupt->SetLevel(oldLevel);
        return;
    }

    // Now we can let the thread wait for the condition variable. Make sure
    // the thread releases the lock before going to sleep.
    conditionLock->Release();
    queue->Append((void *)currentThread);
#ifdef USER_PROGRAM
		if(currentThread->process!=NULL){
			currentThread->process->decreaseActiveThreadCount();
			currentThread->process->increaseWaitThreadCount();
		}
#endif
    currentThread->Sleep();
#ifdef USER_PROGRAM
		if(currentThread->process!=NULL){
			currentThread->process->decreaseWaitThreadCount();
			currentThread->process->decreaseSignalThreadCount();
		}
#endif
    conditionLock->Acquire();

    (void) interrupt->SetLevel(oldLevel);
}

//----------------------------------------------------------------------
// Condition::Signal
// 	Signal the condition variable with a lock. If the thread holding
//      the lock, and there are others waiting for the CV, then take
//      one from the queue and wake it up; otherwise, remove the lock
//      association with the CV.
//----------------------------------------------------------------------
void Condition::Signal(Lock* conditionLock) {
    Thread* thread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    // If the thread trying to signal with the lock isn't the owner
    // of the lock, then do nothing.
    if (!conditionLock->isHeldByCurrentThread()) {
        (void) interrupt->SetLevel(oldLevel);
        return;
    }

    // If no thread is waiting on the condition variable, do nothing.
    if (queue->IsEmpty()) {
        (void) interrupt->SetLevel(oldLevel);
		printf("Signal: No thread waiting.\n");
        return;
    }

    // If the thread is trying to signal other threads, make sure the lock
    // held by the thread matches the one with the condition variable, as
    // other threads are associated with the waiting lock, ie, it's in
    // the same monitor.
    if (waitingLock != conditionLock) {
        //DEBUG('s', "Thread \"%s\" is trying to signal with DIFFERENT lock \"%s\" instead of \"%s\"\n", currentThread->getName(), conditionLock->getName(), waitingLock->getName());
		printf("Thread \"%s\" is trying to signal with DIFFERENT lock \"%s\" instead of \"%s\"\n", currentThread->getName(), conditionLock->getName(), waitingLock->getName());
        (void) interrupt->SetLevel(oldLevel);
        return;
    }

    // If there are threads waiting, wake up the first one as current thread
    // is done with the monitor; otherwise, remove the association with the
    // lock to the condition variable.
    if (!queue->IsEmpty()) {
        thread = (Thread *)queue->Remove();
        if (thread != NULL) {
#ifdef USER_PROGRAM
	if(thread->process!=NULL){
		thread->process->increaseActiveThreadCount();
		thread->process->increaseSignalThreadCount();
	}
#endif
            scheduler->ReadyToRun(thread);
        }
		if (queue->IsEmpty()) {
			waitingLock = NULL;
		}
    }
    else {
        waitingLock = NULL;
    }

    (void) interrupt->SetLevel(oldLevel);
}

//----------------------------------------------------------------------
// Condition::Broadcast
// 	Signal all the threads waiting on the condition variables.
//----------------------------------------------------------------------
void Condition::Broadcast(Lock* conditionLock) {
    while (!queue->IsEmpty()) {
        Signal(conditionLock);
    }
}

//----------------------------------------------------------------------
// Condition::isBusy
// 	Check to see if the condition is being used.
//----------------------------------------------------------------------
bool Condition::isBusy() {
	if (waitingLock != NULL) {
		return TRUE;
	}
	else {
		return FALSE;
	}
}
